This invention relates to an instruction prefetching device for use in a data or information processing system in prefetching an instruction sequence including a branch instruction which may or may not be a branch count instruction.
In prior-art instruction prefetching devices, a considerably long loss cycle is inevitable whenever a branch instruction appears in the instruction sequence and particularly when the branch instruction is a branch count instruction.
An improved instruction prefetching device is described in principle in an article contributed by Erich block et al to IEEE, Computer, April 1978, pages 64-76, under the title of "Component Progress: Its Effect on High-Speed Computer Architecture and Machine Organization" and is disclosed as a practical structure in U.S. patent application Ser. No. 198,990 (now U.S. Pat. No. 4,370,711) filed Oct. 21, 1980, by James Edward Smith. According to Unexamined Publication No. 76, 638 of 1982 of the corresponding Japanese patent application filed by Control Data Corporation, the assignee, prefetch of the instruction sequence is carried out upon appearance of a branch instruction by predicting a branch destination or target based on prior results of actual execution of the branch instruction in question. When the prediction is correct, the prefetch proceeds without the loss cycle. The loss cycle, however, becomes three machine cycles long when the prediction fails. In the manner which will later be described with reference to one of about thirty figures of the accompanying drawing, the loss cycle amounts to a little longer than two machine cycles on the average.
An instruction prefetching device based on a different principle, is revealed in U.S. patent application Ser. No. 415,709 (now U.S. Pat. No. 4,604,691) filed Sept. 7, 1982, by Masanobu Akagi, for assignment to the present assignee. The basic Japanese patent application was filed by NEC Corporation, the assignee, and is published under Unexamined Publication No. 59,253 of 1982. The device includes an instruction cache memory which comprises a plurality of instruction blocks for holding copies of a portion of an instruction area of a main memory. A branch information memory comprises a plurality of information blocks which correspond to the respective instruction blocks. When a branch instruction is held in one of the instruction blocks, the corresponding information block is loaded with a result of execution which has ever been carried out on the branch instruction. Another information block is loaded with an address of an instruction block. The last-mentioned instruction block holds an instruction which should very likely be prefetched next subsequent to the branch instruction. An access to the first-mentioned instruction block and simultaneously to the corresponding information block, is followed by an access to the other information block. An instruction sequence is prefetched at an appreciably high speed. The device is, however, capable of attaining a low accuracy of prefetch due to the prediction by block-to-block correspondence when two or more branch instructions are held in an instruction block.
A later patent application was filed Nov. 16, 1983, under U.S. patent application Ser. No. 552,223 by Syuichi Hanatani et al, including the present applicant and the above-named Masanobu Akagi, for assignment to the instant assignee (EPC Patent Application No. 83 111 451.7). According to the later patent application, an instruction prefetching device is for use in carrying out prefetch of an instruction sequence in a data processing system including an executing unit and comprises a branch history table. In the manner which will later be described more in detail, a plurality of entry pairs are stored in the branch history table. Each entry pair comprises a first and a second entry. The first entry specifies an instruction address of a branch instruction which should be executed by the executing unit prior to prefetch of the instruction sequence. The second entry specifies branch information which comprises a branch destination address obtained by previous execution of the branch instruction. The second entry corresponds to the first entry in this manner as regards each branch instruction. On prefetching an instruction of the instruction sequence, the branch history table is retrieved in search of one of the first entries of the entry pairs in response to a current instruction address of the instruction being prefetched as a current instruction. If one of the first entries is located that specifies an instruction address coincident with the current instruction address, the branch history table produces a corresponding second entry. Prefetch of the instruction sequence is controlled in response to the corresponding second entry. According to the elder patent application, the loss cycle is only one machine cycle long on the average.
The branch instruction may, however, be a branch count instruction which specifies one of a plurality of general purpose registers of the executing unit so as to administrate the number of times of repeated execution of instructions along a loop until a count becomes a predetermined number when the loop is eventually left. In this event, the loss cycle becomes long in the manner which will later become clear.